﻿#include "pch.h"

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
using std::cout;
using std::endl;

int knapsackDP(int capacity, const std::vector<int>& weights, const std::vector<int>& values) {
	const auto n = weights.size();
	std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));

	for (auto i = 1; i <= n; i++) {
		for (int w = 0; w <= capacity; w++) {
			if (weights[i - 1] <= w) {
				dp[i][w] = std::max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
			}
			else {
				dp[i][w] = dp[i - 1][w];
			}
		}
	}

	return dp[n][capacity];
}

TEST(beibao, knapsackDP) {
	std::vector<int> weights = {2, 2, 3, 4, 5};
	std::vector<int> values = {3, 4, 5, 8, 10};
	int capacity = 5;

	int maxValue = knapsackDP(capacity, weights, values);
	std::cout << "Maximum value: " << maxValue << std::endl;
}


struct Item {
	int weight;
	int value;
	double ratio;
};

bool compareByRatio(const Item& a, const Item& b) {
	return a.ratio > b.ratio;
}

int knapsackGreedy(int capacity, const std::vector<Item>& items) {
	std::vector<Item> sortedItems = items;
	for (auto& item : sortedItems) {
		item.ratio = static_cast<double>(item.value) / item.weight;
	}

	std::sort(sortedItems.begin(), sortedItems.end(), compareByRatio);

	int totalValue = 0;
	for (const Item& item : sortedItems) {
		if (capacity >= item.weight) {
			totalValue += item.value;
			capacity -= item.weight;
		}
		else {
			totalValue += item.ratio * capacity;
			break;
		}
	}

	return totalValue;
}


TEST(beibao, knapsackGreedy) {
	std::vector<Item> items = {{2, 3}, {2, 4}, {3, 5}, {4, 8}, {5, 10}};
	int capacity = 5;

	int maxValue = knapsackGreedy(capacity, items);
	std::cout << "Maximum value (greedy): " << maxValue << std::endl;
}


int maxPossibleValue = 0;

void knapsackBranchAndBound(int capacity, int level, int value, const std::vector<Item>& items) {
	if (level == items.size()) {
		maxPossibleValue = std::max(maxPossibleValue, value);
		return;
	}

	if (items[level].weight <= capacity) {
		knapsackBranchAndBound(capacity - items[level].weight, level + 1, value + items[level].value, items);
	}

	knapsackBranchAndBound(capacity, level + 1, value, items);
}

TEST(beibao, knapsackBranchAndBound) {
	std::vector<Item> items = {{2, 3}, {2, 4}, {3, 5}, {4, 8}, {5, 10}};
	int capacity = 5;

	knapsackBranchAndBound(capacity, 0, 0, items);
	std::cout << "Maximum value (branch and bound): " << maxPossibleValue << std::endl;
}


struct ItemB {
	int weight;
	int value;
	int count; // 物品数量上限
};

int knapsackBounded(int capacity, const std::vector<ItemB>& items) {
	int n = items.size();
	std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));

	for (int i = 1; i <= n; i++) {
		for (int w = 0; w <= capacity; w++) {
			int maxItemCount = std::min(w / items[i - 1].weight, items[i - 1].count);
			for (int k = 0; k <= maxItemCount; k++) {
				dp[i][w] = std::max(dp[i][w], dp[i - 1][w - k * items[i - 1].weight] + k * items[i - 1].value);
			}
		}
	}

	return dp[n][capacity];
}

TEST(beibao, knapsackBounded) {
	std::vector<ItemB> items = {{2, 3, 2}, {2, 4, 3}, {3, 5, 2}, {4, 8, 1}, {5, 10, 2}};
	int capacity = 13;

	int maxValue = knapsackBounded(capacity, items);
	std::cout << "Maximum value (bounded knapsack): " << maxValue << std::endl;
}

struct S {
	float weight;
	float maxValue;
	std::vector<int> arrange;
};

/**
 * \brief 是一个这个文档上的方法进行动态规划,这样可以节省时间和空间
 *	https://zhuanlan.zhihu.com/p/30959069
 *
 * \param capacity
 * \param weights
 * \param values
 * \return
 */
std::vector<S> knapsackDPS(float capacity, const std::vector<float>& weights, const std::vector<float>& values) {
	const int n = weights.size();
#if _DEBUG
	std::vector<std::vector<S>> debugVs;
#endif
	std::vector<S> dp(0);
	dp.push_back({0.0, 0.0, std::vector<int>()});
	for (int i = 0; i < n; i++) {
		const float curMax = dp.back().maxValue;
		const int curSize = dp.size();
		for (int k = 0; k < curSize; ++k) {
			const float& newW = dp[k].weight + weights[i];
			const float& newV = dp[k].maxValue + values[i];

			if (newV <= curMax) {
				continue;
			}
			if (newW > capacity) {
				break;
			}
			auto it = std::ranges::find_if(dp, [&](const S& x) {
				return x.weight == newW;
			});
			if (it != dp.end()) {
				if (newV > it->maxValue) {
					it->maxValue = newV;
					it->arrange.push_back(i);
				}
			}
			else {
				const auto& it = std::ranges::find_if(dp, [&](const S& x) {
					return x.weight > newW;
				});
				std::vector<int> copy = dp[k].arrange;
				copy.push_back(i);
				S ss(newW, newV, copy);
				dp.insert(it, ss);
			}
		}
#if _DEBUG
		std::vector<S> copyDp = dp;
		debugVs.push_back(copyDp);
#endif
	}

	return dp;
}

TEST(beibao, knapsackDPS) {
	std::vector<float> ws = {1.1, 2.1, 5.3, 6.4, 7.6};
	std::vector<float> vs = {1.4, 18, 1, 22, 28};
	float capacity = 12.5;

	auto dp = knapsackDPS(capacity, ws, vs);

	float maxValue = dp.back().maxValue;
	std::cout << "Maximum value (knapsackDPS): " << maxValue << std::endl;
	std::cout << "arrange: [";
	for (auto unknown : dp.back().arrange) {
		cout << unknown << ",";
	}
	std::cout << "]" << endl;;
}


int knapsack(int C, std::vector<int> w, std::vector<float> v) {
	int n = v.size();
	std::vector<float> f(C + 1);

	for (int i = 0; i < n; i++) {
		for (int j = C; j >= w[i]; j--)
			f[j] = std::max(f[j], f[j - w[i]] + v[i]);
	}
	return f[C];
}

TEST(beibao, knapsack) {
	std::vector<int> ws = {1, 2, 5, 6, 7};
	std::vector<float> vs = {1, 16, 8, 22, 28};
	int capacity = 11;

	float maxValue = knapsack(capacity, ws, vs);

	std::cout << "Maximum value (knapsack): " << maxValue << std::endl;
}


TEST(beibao, duibi) {
	std::vector<int> ws = {422, 422, 422, 422, 422, 422, 422, 422, 422, 422, 422, 709, 709, 709, 709, 709, 709, 709, 709, 709, 709, 709};
	std::vector<float> vs = {422, 422, 422, 422, 422, 422, 422, 422, 422, 422, 422, 709, 709, 709, 709, 709, 709, 709, 709, 709, 709, 709};
	int capacity = 12000;

	float maxValue = knapsack(capacity, ws, vs);

	std::cout << "Maximum value (knapsack): " << maxValue << std::endl;
}

template <typename T>
std::vector<T> ReArr(std::vector<T> source, std::vector<int> indices) {
	std::vector<T> arr1;
	std::vector<T> arr2;
	for (auto idx : indices) {
		arr1.push_back(source.at(idx));
	}
	int idx = 0;
	for (auto element : source) {
		if (std::ranges::find(indices, idx) == indices.end()) {
			arr2.push_back(element);
		}
		idx++;
	}
	arr1.insert(arr1.end(), arr2.begin(), arr2.end());
	return arr1;
}

TEST(vector, ReArr) {
	std::vector<int> source = {1, 3, 4, 5, 76, 8, 9, 0, 0};
	std::vector<int> ids = {1, 2, 5};
	auto res = ReArr(source, ids);

	for (auto value : res) {
		cout << value << ",";
	}
}


TEST(vector, Sort) {
	std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

	auto print = [&s](std::string_view const rem) {
		for (auto a : s)
			std::cout << a << ' ';
		std::cout << "：" << rem << '\n';
	};

	std::sort(s.begin(), s.end());
	print("用默认的 operator< 排序");

	std::sort(s.begin(), s.end(), std::greater<int>());
	print("用标准库比较函数对象排序");

	struct {
		bool operator()(int a, int b) const { return a < b; }
	} customLess;

	std::sort(s.begin(), s.end(), customLess);
	print("用自定义函数对象排序");

	std::sort(s.begin(), s.end(), [](int a, int b) {
		return a > b;
	});
	print("用 lambda 表达式排序");
}

inline struct BoundedBox {
	float weight;
	float maxValue;
	std::vector<std::pair<int, int>> arrange;
};


/**
   * @brief 多重背包问题的算法 
   * @author: lianbo
*/
std::vector<BoundedBox> bounded_knapsackDPS(float capacity, const std::vector<float>& weights, const std::vector<float>& values, const std::vector<int>& nums) {
	const auto n = weights.size();
#if _DEBUG
	std::vector<std::vector<BoundedBox>> debugVs;
#endif
	std::vector<int> ava_nums;
	for (auto i = 0; i < n; ++i) {
		int max_cap_item = static_cast<int>(capacity / weights[i]);
		if (nums[i] < max_cap_item) {
			ava_nums.push_back(nums[i]);
		}
		else {
			ava_nums.push_back(max_cap_item);
		}
	}
	std::vector<BoundedBox> dp(0);
	dp.push_back({0.0, 0.0, std::vector<std::pair<int, int>>()});
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < ava_nums[i]; j *= 2) {
			const float curMax = dp.back().maxValue;
			const int curSize = dp.size();
			for (int k = 0; k < curSize; ++k) {
				const float& newW = dp[k].weight + weights[i] * j;
				const float& newV = dp[k].maxValue + values[i] * j;

				if (newV <= curMax) {
					continue;
				}
				if (newW > capacity) {
					break;
				}
				auto it = std::ranges::find_if(dp, [&](const BoundedBox& x) {
					return x.weight == newW;
				});
				if (it != dp.end()) {
					if (newV > it->maxValue) {
						it->maxValue = newV;
						it->arrange.push_back(std::make_pair(i, j));
					}
				}
				else {
					const auto& it = std::ranges::find_if(dp, [&](const BoundedBox& x) {
						return x.weight > newW;
					});
					auto copy = dp[k].arrange;
					copy.push_back(std::make_pair(i, j));
					BoundedBox ss(newW, newV, copy);
					dp.insert(it, ss);
				}
			}
		}
#if _DEBUG
		std::vector<BoundedBox> copyDp = dp;
		debugVs.push_back(copyDp);
#endif
	}

	return dp;
}
